The Inns of Telengard are located above all stairways on Dungeon Level 1. Characters entering an inn will spend the night and regain all lost hit points and used spell units. In addition, characters automatically deposit all gold upon entering an inn and may advance to a higher experience level.

With the exception of the Worthy Meade Inn, it seems like you never enter the same inn twice.  That's because there are a total of 900 different Inn names, created by combining words from the following table (notice INN is listed twice):