The government won by only two votes - 160-158 - after turning the issue into one of confidence, in order to unite its fractious coalition.
The security package must now be passed by the lower house to become law.
The measure was adopted last month, after the murder of a woman in Rome, allegedly by an immigrant from Romania.
The Interior Minister, Giuliano Amato, had threatened to resign if the decree was not approved by parliament.
The confidence vote was announced by the minister for relations with parliament, Valentino Chiti, when it became clear that certain clauses of the decree were in danger of being rejected.
"The government wanted an open and constructive confrontation and also a convergence between majority and opposition," Mr Chiti said in his statement.
"It has not been possible. At this point, the government thinks the coherence of the decree agreed with its majority must be conserved."
Legislators from the opposition centre-right alliance had predicted the vote would cause the collapse of Prime Minister Romano Prodi's fractious centre-left coalition, which has only a two-seat Senate majority.
"For a matter as sensitive as this one for the country, one that affects citizens so nearly, such as law and order, the thought of subjecting it to a vote of confidence means the end of this political majority," Mario Baccini said.
Some left-wing senators are uneasy with some of the provisions of the decree, adopted on a wave of public indignation after the brutal murder of Giovanna Reggiani in late October.
An ethnic Roma from Romania, Nicolae Romulus Mailat, is on trial for that murder.
Some 117 deportation orders have been served against Romanian citizens since the adoption of the decree, Corriere della Sera newspaper reported.