Malnutrition is common, morbid, and often correctable, but subject to missed and delayed diagnosis. Better screening and prediction could improve clinical, functional, and economic outcomes. This study aimed to assess the predictability of malnutrition from longitudinal patient records, and the external generalizability of a predictive model. Predictive models were developed and validated on statewide emergency department (ED) and hospital admission databases for California, Florida and New York, including visits from October 1, 2015 to December 31, 2018. Visit features included patient demographics, diagnosis codes, and procedure categories. Models included long short-term memory (LSTM) recurrent neural networks trained on longitudinal trajectories, and gradient-boosted tree and logistic regression models trained on cross-sectional patient data. The dataset used for model training and internal validation (California and Florida) included 62,811 patient trajectories (266,951 visits). Test sets included 63,997 (California), 63,112 (Florida), and 62,472 (New York) trajectories, such that each cohort's composition was proportional to the prevalence of malnutrition in that state. Trajectories contained seven patient characteristics and up to 2,008 diagnosis categories. Area under the receiver-operating characteristic (AUROC) and precision-recall curves (AUPRC) were used to characterize prediction of first malnutrition diagnoses in the test sets. Data analysis was performed from September 2020 to May 2021. Between 4.0% (New York) and 6.2% (California) of patients received malnutrition diagnoses. The longitudinal LSTM model produced the most accurate predictions of malnutrition, with comparable predictive performance in California (AUROC 0.854, AUPRC 0.258), Florida (AUROC 0.869, AUPRC 0.234), and New York (AUROC 0.869, AUPRC 0.190). Deep learning models can reliably predict malnutrition from existing longitudinal patient records, with better predictive performance and lower data-collection requirements than existing instruments. This approach may facilitate early nutritional intervention via automated screening at the point of care.