Yes, of course we (believers) do. Paradise was understood by the Jews as a place where the disembodied souls of the righteous go and Jesus using that notion promised it instantly upon death.
Paradise was understood at the time of Christ as place where the saints would go after dying in a disembodied state. In other words the soul would go to paradise, if you were good. The soul of the wicked would go to hell in Hades. In old Greek paradise originally referred just to a royal park. The Jews borrowed the word giving it a spiritual meaning as the 'garden of God' and then used it to refer to a restored 'garden of Eden' which was a place where righteous disembodies souls went.
For example in the Jewish writings just before Christ concerning the Messiah we find:
And he shall open the gates of paradise, And shall remove the threatening sword against Adam. And he shall give to the saints to eat from the tree of life (Testimony of Levi 18:10-11)
In Eden God put a sword to keep Adam away from the tree of life after he sinned, but in paradise man would be restored to Eden again.
Jesus would have been guilty of greatly confusing the poor thief dying on the cross of a 'promised paradise' (as the man understood it) if there was actually no actual wonderful place for disembodies souls to go until the time of the resurrection!
Then he said, “Jesus, remember me when you come into your kingdom.”
Jesus answered him, “Truly I tell you, today you will be with me in paradise.” (Luke 23:42-43, NIV)
Clearly Jesus is telling the man that today (with reference to literal time he will enter the restored garden of Eden. There is no real logical interpretation but that paradise was where Jesus would be and that the man would go their without his body to be with him. The man would not be unconscious until the resurrection but have full clarity of mind.
The same assumption of immediacy is asserted everywhere the idea is approached. When Stephen was being stoned to death in Acts, he had a vision of heaven and called out, 'Lord Jesus, receive my spirit' insinuating an immediate sense. In Philippians 1:23 Paul compares what is better to be in the body, or be with the Lord without the body. Similarly in 2 Corinthians 5:8, Paul says to be away from the body is to be with the Lord. The idea is immediate and the idea is that in heaven we are without the body.
Both paradise and hell are considered the intermediate state where disembodied souls are waiting for the resurrection of the body. Then after the resurrection of the body the dead and the living will be judged. In Revelation Ch 20 and 21 we see these temporary places are renovated for final residence. Hell is thrown into the 'lake of fire' as the final judgement of the wicked and a new heaven and a new earth are created for the children of God. So Christ's return is not about bringing souls into heaven but raising their bodied to be united back to their souls that they might live on a new earth filled with a perfect endless heaven. They were never meant to be disembodied forever, even in the bliss of paradise. We are meant to have an eternal soul and body, bit just a soul.
With respect to the body in the grave, which will be resurrected when Christ appears means the body is only taking a nap. The idea is that when Christ returns, first those who are in heaven [those whose bodies are napping] will assume a new body and will meet him in the air. Then all the those still in the body on earth, will also have a resurrected body. Then the final judgment.
According to the Lord’s word, we tell you that we who are still alive, who are left until the coming of the Lord, will certainly not precede those who have fallen asleep. For the Lord himself will come down from heaven, with a loud command, with the voice of the archangel and with the trumpet call of God, and the dead in Christ will rise first. After that, we who are still alive and are left will be caught up together with them in the clouds to meet the Lord in the air. And so we will be with the Lord forever. (1 Thessalonians 4:15-17, NIV)