We describe in this paper a new binary millisecond pulsar, PSR J1738+0333. Using Arecibo, we have achieved good timing accuracy for this object, about 220 ns for 1-hour integrations over 100 MHz. This allowed us to measure a precise proper motion, parallax and orbital parameters for this system. We highlight the system's potential for constraining alternative theories of gravitation.