Many real-world applications for robots-such as long-term aerial and underwater observation, cross-medium operations, and marine life surveys-require robots with the ability to move between the air-water boundary. Here, we describe an aerial-aquatic hitchhiking robot that is self-contained for flying, swimming, and attaching to surfaces in both air and water and that can seamlessly move between the two. We describe this robot's redundant, hydrostatically enhanced hitchhiking device, inspired by the morphology of a remora (Echeneis naucrates) disc, which works in both air and water. As with the biological remora disc, this device has separate lamellar compartments for redundant sealing, which enables the robot to achieve adhesion and hitchhike with only partial disc attachment. The self-contained, rotor-based aerial-aquatic robot, which has passively morphing propellers that unfold in the air and fold underwater, can cross the air-water boundary in 0.35 second. The robot can perform rapid attachment and detachment on challenging surfaces both in air and under water, including curved, rough, incomplete, and biofouling surfaces, and achieve long-duration adhesion with minimal oscillation. We also show that the robot can attach to and hitchhike on moving surfaces. In field tests, we show that the robot can record video in both media and move objects across the air/water boundary in a mountain stream and the ocean. We envision that this study can pave the way for future robots with autonomous biological detection, monitoring, and tracking capabilities in a wide variety of aerial-aquatic environments.