Locomotion is an essential feature for survival of many organisms, and it is also a technical requirement for untethered biomedical microdevices to operate inside the human body for targeted drug delivery and minimally invasive surgery. The overall goal of this thesis is to develop microdevices that are capable of actively propelling themselves through and performing tasks in complex biological fluids. Two major challenges are encountered: the complex fluidic environment and the small length scale. The first part of the thesis addresses the first challenge: the diverse rheological properties of biological fluids. Most biological fluids are non-Newtonian, and to move in these fluids, the propulsion scheme is highly dependent on the size of the device: 1) When it is comparable or smaller than the mesh size of the biopolymeric network, then the device experiences purely viscous drag, thus the schemes for propulsion in Newtonian fluids will still be effective. To study the active microrheology of porous biological fluids, a magnetic tweezer set-up is constructed to pull magnetic beads of varying size through the porcine vitreous. It is found that for unhindered propulsion through the vitreous, nanodevices with a cross-section of less than 500 nm are needed. 2) When the size of the device is larger than the fluidic mesh size, non-Newtonian properties of the fluid become important and can be utilized for propulsion. We design the first symmetric micro-swimmer actuated by reciprocal motion and demonstrate its propulsion in biologically-relevant fluids. A larger scale low Reynolds number swimmer model is also built and excellent agreement between measurements and theory indicates that the net propulsion is caused by modulation of the fluid viscosity upon varying the shear rate. It opens new possibilities of using a simple actuation scheme for propulsion in non-Newtonian biological fluids. The second challenge is the small size of the device which severely limits the choice of available miniaturized actuators. We explore a novel wireless ultrasonic actuation scheme and a prototype is tested for application in the urinary tract. In order to test the prototype, a general technique is first developed to build a phantom of the human kidney. Based on high resolution medical imaging data, a three dimensional (3D) model is constructed using 3D printing and polymer casting techniques. The phantom not only faithfully reproduces the anatomical structural details, but also mimics the mechanical properties of the real tissue. To address the challenge of powering untethered microdevices, a novel bubble array streaming surface (BASS) actuator is developed. Under ultrasonic excitation, the oscillation of micro gas bubbles results in acoustic streaming and provides a propulsive force that drives the device. Ultrasonic actuators with different bubble sizes are fabricated, and individual driving frequency and propulsive force are measured. The actuator operates as an end-effector of a miniaturized endoscope, which has a cross-sectional side length of only 1 mm, thinner than the endoscopes currently in use. The tip of the end-effector is equipped with a miniaturized camera, its orientation is controlled wirelessly by the actuator, and active cystoscopy is successfully performed inside a rabbit bladder. Miniaturized medical instruments and micro-robots will benefit from the wireless actuation schemes demonstrated herein.