We present a new evolution of the Very Little Eel-Inspired roBot, the VLEIBot++, a 900-mg swimmer driven by two 10-mg bare high-work density (HWD) actuators, whose functionality is based on the use of shape-memory alloy (SMA) wires. An actuator of this type consumes an average power of about 40 mW during in-air operation. We integrated onboard power and computation into the VLEIBot++ using a custom-built printed circuit board (PCB) and an 11-mAh 3.7-V 507-mg single-cell lithium-ion (Li-Ion) battery, which in conjunction enable autonomous swimming for about 20 min on a single charge. This robot can swim at speeds of up to 18.7 mm/s (0.46 Bl/s) and is the first subgram microswimmer with onboard power, actuation, and computation developed to date. Unfortunately, the approach employed to actuate VLEIBot++ prototypes is infeasible for underwater applications because a typical 10-mg bare SMA-based microactuator requires an average power on the order of 800 mW when operating underwater. To address this issue, we introduce a new 13-mg power-efficient high-performance SMA-based microactuator that can function with similar power requirements (approx. 80 mW on average) and actuation performance (approx. 3 mm at low frequencies) in air and water. This design is based on the use of a sealed flexible air-capsule that encloses the SMA wires that drive the microactuator with the purpose of passively controlling the heat-transfer rate of the thermal system. Furthermore, this new power-efficient encapsulated actuator requires low voltages of excitation (3 to 4 V) and simple power electronics to function. The breakthroughs presented in this paper represent a path towards the creation of insect-scale autonomous underwater vehicles (AUVs).