Check if the IMEI is blacklisted first. If that's the case, it's usually because of a unpaid balance or the phone was stolen. Either way the IMEI is “branded” for good. To avoid wasting time, check the status of the IMEI on Swappa. Since we now have global blacklists the phone is useless everywhere; even for international use.
If the IMEI is bad because it's actually stolen, take the phone to the police and see if you can get it legally by giving the owner a chance to reclaim it. This isn't always possible but most states allow for this. It usually means the police hold the phone, so be prepared for that.
If it's stolen and you get it keep it this way do not expect the carrier to help you make it usable as a phone; that IMEI# is never going to be good again. Even if you can fix the IMEI by replacing it, I wouldn't recommend this because it's a legal grey area.
If the IMEI comes up clean, do a Recovery Mode restore. If that works, it was something with the baseband that caused the issue that was recoverable. It's usually a carrier software problem when this works. Follow this guide to access Recovery Mode: iPhone/iPod/iPad Recovery Mode Restore
If the Recovery Mode restore doesn't fix the phone, it's a hardware baseband problem. The motherboard will need to be replaced since the baseband is typically paired. The boards usually cost as much a whole phone so it may not be worth it to replace the board. That said, if you do swap the board you should try and check the IMEI if you can do so. I’d also STRONGLY RECOMMEND getting the matching back so the phone and board have the same identity, to avoid problems in the future. It typically doesn’t matter but if a carrier or secondhand buyer sees it, it doesn’t always come off well. I’m not bothered by it to the extent I will run away from the phone, but it is a red flag that something is up in most cases. I’m going to check the IMEI per the board anyway, so it’s kind of moot but I like to see matching identities.