More than half of the deaths from cardiovascular diseases (CVDs) can be eliminated if high Blood Pressure (BP) is brought under control. Towards this target, continuous BP monitoring is a must. Unfortunately, such continuous monitoring is hindered by the inconvenience of the traditional cuff-based method. Convolutional Neural Networks (CNNs) offer a promising alternative to address such problems. Nonetheless, existing CNN-based solutions rely on server-like infrastructure with huge computation and memory capabilities. This entails these solutions impractical with several security, privacy, reliability, and latency concerns. The contribution of this paper is twofold as follows. First, the paper contributes to the general field of tinyML by proposing novel techniques that enable the fitting of popular CNNs into extremely-constrained edge devices with limited computation, memory, and power budget. Namely, the paper successfully manages to fit the following five popular CNNs into tiny edge devices: AlexNet, LeNet, SqueezeNet, ResNet, and MobileNet. This enables us to run inference completely on the edge without dependency on connectivity or cloud infrastructure. The proposed techniques use a combination of novel architecture modifications, pruning, and quantization methods. Second, utilizing this stepping stone, the paper proposes a tinyML-based solution to enable accurate and continuous BP estimation using only photo-plethysmogram (PPG) signals. We conduct an extensive evaluation using thousands of real Intensive Care Unit (ICU) patient data and several tiny edge devices and all the five aforementioned CNNs. Results show that the proposed solutions offer comparable accuracy to server-based solutions, and also meet the Association for the Advancement of Medical Instrumentation (AAMI) and the British Hypertension Society (BHS) standards.