^ Depends on the state you live in. Some states (such as California, the state I live in) are "two-party consent" states. Meaning, both parties have to consent to being recorded otherwise it is illegal. Some states are only one-party consent states, which means only one party has to consent to being recorded and the other does not.
Federal law is only one party consent. However, there was a supreme court decision upholding that California's two-party consent applies if the calls are made to California from another state (in that case, Georgia).
California "Two-Party Consent Law" Applies to Recording of Calls Made from Other States | Resources | Morrison Foerster
Now I'm not 100% sure when I say this bit but; I remember working on a project that I had to do some research on for calling another one-party state FROM California and I believe that was ok (as in, I could be the party consenting while the other did not have to).
Hope this helps, stumbled on here clicking around lol.