Determining similarities (or distance) between multivariate time series sequences is a fundamental problem in time series analysis. The complex temporal dependencies and variable lengths of time series make it an extremely challenging task. Most existing work either rely on heuristics which lacks flexibility and theoretical justifications, or build complex algorithms that are not scalable to big data. In this paper, we propose a novel and effective metric learning model for multivariate time series, referred to as Deep ExpeCted Alignment DistancE (DECADE). It yields a valid distance metric for time series with unequal lengths by sampling from an innovative alignment mechanism, namely expected alignment, and captures complex temporal multivariate dependencies in local representation learned by deep networks. On the whole, DECADE can provide valid data-dependent distance metric efficiently via end-to-end gradient training. Extensive experiments on both synthetic and application datasets with multivariate time series demonstrate the superior performance of DECADE compared to the state-of-the-art approaches.