Physical evolutions are always unitary. Thus, in order to implement a non-unitary gate, you need to add an ancilla system, perform a big (deterministic) unitary on the total system + ancilla, and then measure the ancilla. Depending on the measurement outcome, this will result in a non-unitary gate applied to the system.
Thus, you only get the desired gate applied to the system for a particular measurement outcome, and thus, the gate is non-deterministic.
Note, however, that there is also the class of trace-preserving CP maps, which can also be applied deterministically, but they will generally map pure state to mixed states -- except for the map which discards whatever input you have and always outputs the same pure state. (However, this map can not be understood as a linear map on the level of pure state, i.e. vectors in Hilbert space.)