The focus of this research is on the estimation of traffic density from data obtained from Connected and Autonomous Probes (CAPs). CAPs pose an advantage over expensive and invasive infrastructure such as loop detectors. CAPs maneuver their driving trajectories, sensing the presence of adjacent vehicles and distances to them by means of several electronic sensors, whose data can be used for more sophisticated traffic density estimation techniques. Traffic density has a highly nonlinear nature during on-congestion and queue-clearing conditions. Closed-mathematical forms of the traditional density estimation techniques are incapable of dealing with complex nonlinearities, which opens the door for data-driven approaches such as machine learning techniques. Deep learning algorithms excel in data-rich contexts, which recognize nonlinear and highly situation-dependent patterns. Our research is based on an LSTM (Long short-term memory) neural network for the nonlinearity associated with time dynamics of traffic flow. The proposed method is designed to learn the input-output relation of Edie’s definition. At the same time, the method recognizes a temporally nonlinear pattern of traffic. We evaluate our algorithm by using a microscopic simulation program (PARAMICS) and demonstrate that our model accurately estimates traffic density in Free-flow, Transition, and Congested conditions.