In this paper, we propose a sojourn time based maximum likelihood (ML) estimation technique for accurately estimating the velocity of mobile users in Heterogeneous Networks (HetNets). In such networks, base station (BS) density in a particular area is more compared to the traditional macrocell network for better quality of service. However, increase in BS density results in more frequent handovers, and thus causes handoff failures. To address these challenges, knowledge of mobile user's velocity is a significant requirement. In this work, we develop a velocity estimation strategy based on sojourn time. Sojourn time is defined as the time span in which a user is served by one BS before it handed over to another BS for better services. The sojourn time method is used in this analysis as it considers both handover count and sojourn time information in estimating the user velocity. Here, we consider that BSs are randomly distributed by homogeneous Poisson point process (PPP), and their coverage is modeled by using Poisson-Voronoi tessellation. Using these statistics, we first derive the Cramer-Rao Lower Bound (CRLB) based on sojourn time and later we determine an ML estimator, which is asymptotically unbiased. We validate our approach by simulation in which we show the tight closeness of ML estimator asymptotic variance with CRLB. Also, we compare the proposed ML estimator with CRLB of velocity estimator based on sojourn time and handover count. Our results illustrate that proposed ML estimator based on sojourn time outperforms the CRLB based on handover count.