Abstract Wireless Body area networks (WBANs) consist of sensors that continuously monitor and transmit real time vital signals to a nearby coordinator and then to a remote terminal via the Internet. One of the most important signals for monitoring in WBANs is the electrocardiography (ECG) signal. The design of an accurate and energy efficient ECG telemonitoring system can be achieved by: i) reducing the amount of data that should be transmitted ii) minimizing the computational operations executed at any transmitter/receiver in a WBAN. To this end, compressed sensing (CS) approaches can offer a viable solution. In this paper, we propose two novel CS based ECG reconstruction algorithms that minimize the samples that are required to be transmitted for an accurate reconstruction, by exploiting the block structure of the ECG in the time domain (TD) and in an uncorrelated domain (UD). The proposed schemes require the solutions of second - order cone programming (SOCP) problems that are usually tackled by computational demanding interior point (IP) methods. To solve these problems efficiently, we develop a path-wise coordinate descent based scheme. The reconstruction accuracy is evaluated by the percentage root-mean-square difference (PRD) metric. A reconstructed signal is acceptable if and only if P R D < 9 % . Simulation studies carried out with real electrocardiographic (ECG) data, show that the proposed schemes, operating in both the TD and in the UD as compared to the conventional CS techniques, reduce the Compression Ratio (CR) by 20 % and 44 % respectively, offering at the same time significantly low computational complexity.