The sun still rises in the East and sets in the West. So you quickly identify the cardinal directions.
By observing the point around which the stars rotate each night you can find the altitude of the pole, which gives you your latitude. You can't find your absolute longitude, but with good time keeping you can find your longitude relative to your starting point. The planets are still in the same orbits. You might find that Saturn doesn't have rings (it's not certain how old the rings are)
The Galaxies would still be in the same positions, The Milkyway, Andromeda and the Magellanic clouds are all visible. Many more with a moderate telescope, The Milkyway would look different, in detail, the LMC and SMC would be in different positions.
However, the stars in the background have all changed. There are no constellations that have not undergone radical changes. There would be no stars that you recognise: Stars are visible either because they are close (and so have a large proper motion) or powerful and short-lived. All the stars you know would either have moved, or not be born yet.