We provide the first behavioral characterization of nested logit, a foundational and widely applied discrete choice model, through the introduction of a non-parametric version of nested logit that we call Nested Stochastic Choice (NSC). NSC is characterized by a single axiom that weakens Independence of Irrelevant Alternatives based on revealed similarity to allow for the similarity effect. Nested logit is characterized by an additional menu-independence axiom. Our axiomatic characterization leads to a practical, data-driven algorithm that identifies the true nest structure from choice data. We also discuss limitations of generalizing nested logit by studying the testable implications of cross-nested logit.