I think it is tax deductible.
See this link for H1B case:
http://www.immigration.com/faq/irs.html#53
Q21 I was wondering if I could claim all my legal expenses for tax return documents that I had to pay for H-1B application in the year 2001 and 2003. I heard from some people that I am not supposed to since it has to be paid by the company, but in my case I paid the full amount (both legal expenses and USCIS fee) and my accountant says that I should definitely claim them.
A21 You can deduct the expenses as Unreimbursed Employee Business Expenses on Form 1040-Schedule A. The deduction will be subject to 2% Adjusted Gross Income limit.