This paper proposes a new identification and estimation approach to semi-parametric multinomial choice models that easily applies to not only cross-sectional settings but also panel data settings with unobservable fixed effects. Our approach is based on cyclic monotonicity, which is a defining feature of the random utility framework underlying multinomial choice models. From the cyclic monotonicity property, we derive identifying inequalties without requiring any shape restriction for the distribution of the random utility shocks.  These inequalities point identify model parameters under straightforward assumptions on the covariates.  We proposed a consistent estimator based on these inequalities, and apply it to a panel data set to study the determinants of the demand of bathroom tissue.