Devices and methods for cooling all or part of the body of a human or animal subject by inserting a heat exchange catheter into the subject's body and infusing into or through the catheter a heat exchange medium that contains liquid phase matter and frozen solid phase matter, wherein at least some of the solid phase matter melts while in the catheter.