I frequently start in an underground parking garage with no cell or GPS, and have no trouble at all getting Waze to route me to places I've been before, calling up from my destination history or favorites. When I'm outside and have a cell connection and get GPS, Waze will then recalculate my route. This is my experience on the Android platform in the US, iOS may be different, and other countries may be different.
What will not work is to attempt to do a new search, or to drive to a destination that goes through map tiles that are not on your device. And no, the map is not always on your device. When you get navigation directions from the server, your device should update its tiles that are used in that route, and when you drive into areas that aren't cached in your device, it will also attempt to load map tiles then. If you drive a lot without navigation, you may find that your map tiles go stale and don't update, and you may need to force them to reload if there have been changes to the map in your area.
You will run into problems if Waze thinks it may have internet connection when it does not. Then you will get a server timeout, and may not get routing to your destination, even when calling it up from history.
Last edited by slandrum
on Tue Jan 21, 2014 9:53 pm, edited 1 time in total.
Orange County, CA, USA, Samsung Galaxy S3, Android 4.3