I work with a team on a complex web service and agree with all of Steve K's points. A REST-like approach using appropriate HTTP verbs and a good resource design are (given the right use-case) a big win. The problem for me with HATEOS evangelists is that they seem to think it solves more problems than it actually does. Sure, we now have a layer of abstraction between logical and http link but for anything other than trivial changes you always have to have human readable documentation. HATEOS works brilliantly for the web because there is a human at other other end who understands what "new comment" is and how it's different from "new private message". My customers' API clients don't have this semantic understanding. Now I know that it helps dev's if they can navigate around my API but it's no substitute for well written documentation; HATEOS API's are something to strive for but not self-describing as some claim.