To accommodate the requirements such as high usability and personalization of 4G (mobile) networks, conventional handheld single network-interface mobile devices are evolving into multi-homed devices. Moreover, owing to the recent advances in the mobile middleware technologies, hardware technologies and association with the human user, handheld mobile devices are evolving into data producers and in turn acting as Nomadic Mobile Service (NMS) providers. For these devices, a vertical handover support is essential for the improved and reliable NMS delivery. Also, the fulfillment of the required QoS by the NMS is bounded by the end-to-end QoS (e2eQoS) provided by the underlying heterogeneous networks. To deal with these aspects, we propose a context-aware middleware architecture supporting vertical handover for the NMSs hosted on the handheld mobile devices. We emphasize the following features of the proposed middleware: 1) Context-aware computing based approach which uses an extensive set of context information collected from the mobile device and a fixed network; 2) Provisioning of and interaction with the end-to-end QoS (e2eQoS) predictions context source in the fixed network to obtain near-accurate estimation of the e2eQoS at a certain geographic location and to reduce unnecessary power usage in searching for available networks.