Thanks for your inquiry. The best advice would be to consult with an experienced attorney who is not going to steal you blind and who will advise you about the important developments in the law with regards to the situation you have presented.
The problem is that it sound like your significant other spent a significant period of time in the US without lawful status. So when he was deported and removed, he like triggered a ten year bar which prevents foreign nationals from returning to the US for a period of ten years as a result of having accrued a period of one year or more of "unlawful presence" here in the US. Likewise, there would be a ten year bar that would apply to him as a result of having been deported from the US.
Both of these bars have solutions, commonly referred to as "waivers." A waiver would be available if you were to get married and may be available if you do not get married but instead decide to do this as a fiance visa. I think that my general recommendation would be to get married, it just makes it easier.
Currently, the process of applying for these waivers is going through some changes. These changes, however, have not fully been implemented and we are actually in a period of transition from the old system to a newer (hopefully less complicated) system. The old system was that your significant other would appear for an appointment at the US Consular Office (USCON) where his application for a visa would be denied (keep in mind that prior to getting this appointment, there would be a requirement of filing applications for the approval of a visa through Citizenship and Immigration Services (CIS) here in the US).
When the visa is denied, your significant other could apply for the waivers and that application would be sent from the USCON to the CIS office abroad which would then make a determination on whether the visa would be issued. The process took forever and no one knew how long their loved one would spend outside of the US waiting for the requested waivers to be adjudicated. While the approval rates were high (especially through Mexico), it took forever).
The process that is being transitioned to is one where the waiver applications would be filed here in the US. This way, the loved one would know what they are going to receive when they go to the USCON and this in turn was aimed at making the waiting periods shorter. Currently, there is a process of transition going on with these applications and the system of adjudicating the waiver applications will depend on the system that is in place when you are ready to submit the applications to CIS.
So the issues that your significant other has are fixable, but I would highly recommend spending the time and the money on hiring someone who is reputable and has experience handling these matters. There are a lot of folks out there making all sorts of promises, many of which are untrue and which will end up with nothing more than funds being spent on services that will lead nowhere. I do not mean to give a negative description of those of us out there in the business, but with this period of transition there has been lots of BS out there and you really need to be careful.
Reputable attorneys are folks who can verify that they are licensed. They are folks who have a real office. They are attorneys ho are not afraid to speak with you and who will answer your questions. The decision on who you hire is always up to you, never feel like you are being forced into anything. There are solutions out there for the situation that you have discussed and it is imperative that you find someone who can do what needs to be done in this case.
Keep in mind as well that this advice is based on what you have shared. If there are other concerns in this case (i.e. criminal convictions or more frequent immigration violations), the answer I have provided may not be all that correct. Open up with the attorney you choose and tell him/her everything. Good luck
Just to clarify, this is a male/female relationship?
If so, your husband-to-be will need an extreme hardship waiver of the deportation bar and any other bar that may pertain to his case (unlawful presence, for example).
You don't want to attempt this without experienced help. My firm focuses on waivers and I represent clients nationally. Feel free to contact me at Veronica@tunitskylaw.com if you'd like to consult.
The information offered is general in nature and not meant to be relied upon as legal advice. Please consult an attorney prior to making legal decisions. Visit us at www.tunitskylaw.com. Contact us at 713.335.5505 or email at firstname.lastname@example.org. Veronica Tunitsky offers in-person, as well as telephone and email consultations.